import java.util.List;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-19
 * Time: 18:14
 */
class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val){
        this.val=val;
    }
}
public class Solution {
    //反转链表
    public ListNode reserve(ListNode head){
        if(head==null){
            return null;
        }
        ListNode newHead=null;
        ListNode cur=head;
        while (cur!=null){
            ListNode curNext=cur.next;
            cur.next=newHead;
            newHead=cur;
            cur=curNext;
        }
        return newHead;
    }
    public ListNode addInList (ListNode head1, ListNode head2) {
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        //先翻转两个链表，因为加法是从低位到高位的，低位在链表表尾，不翻转的话没法进位，单链表不可以逆序
        //所以我们可以从翻转后的表头开始，此时就是低位开始相加了
        head1=reserve(head1);
        head2=reserve(head2);
        //定义新的相加的链表表头
        ListNode newH=new ListNode(-1);
        ListNode head=newH;
        int carry=0;
        //构造链表
        while (head1!=null || head2!=null || carry!=0){  //只要有链表不为空或者两个链表为空了，但是进位不为空就还可以构造
            int val1=head1==null ? 0:head1.val;
            int val2=head2==null ? 0:head2.val;
            int sum=val1+val2+carry; //将两个节点值和进位相加
            carry=sum/10;//进位
            sum%=10;//最终的每一位的值
            //构造节点
            head.next=new ListNode(sum);
            head=head.next;
            //两个链表往下走
            if(head1!=null){
                head1=head1.next;
            }
            if(head2!=null){
                head2=head2.next;
            }
        }
        //构造完后，还需要翻转一下
        return reserve(newH.next);
    
    }
}
